package dp.subsequence;

/**
 * 给两个整数数组A和B，返回两个数组中公共的、长度最长的子数组的长度。
 *
 * 
 *
 * 示例：
 *
 * 输入：
 * A: [1,2,3,2,1]
 * B: [3,2,1,4,7]
 * 输出：3
 * 解释：
 * 长度最长的公共子数组是 [3, 2, 1] 。
 */
public class leetCode718_findLength {
    public static void main(String[] args) {
        int[] n = {1,2,3,2,1};
        int[] m = {3,2,1,4,7};
        leetCode718_findLength a = new leetCode718_findLength();
        int length3 = a.findLength3(n, m);
        System.out.println(length3);
    }
    public int findLength(int[] nums1, int[] nums2) {
        if(nums1.length == 0 || nums2.length == 0){
            return 0;
        }
        int result = 0;
        int[][] f = new int[nums1.length + 1][nums2.length + 1];
        // 之所以从大到小遍历，是因为从小到大遍历，对于i-1非常难处理。
        for (int i = nums1.length - 1; i >= 0; i--) {
            for (int j = nums2.length - 1; j >= 0;j--) {
                if(nums1[i] == nums2[j]) {
                    f[i][j] = f[i + 1][j + 1] + 1;
                    if(result < f[i][j]){
                        result = f[i][j];
                    }
                }
            }
        }
        return result;
    }

    /**
     * dp[i][j] 表示nums1在i - 1之前，nums2在j - 1之前的最长重复子数组的长度
     * @param nums1
     * @param nums2
     * @return
     */
    public int findLength2(int[] nums1, int[] nums2) {
        int result = 0;
        if(nums1.length == 0 || nums2.length == 0) return 0;
        int[][] dp = new int[nums1.length + 1][nums2.length + 1];
        for (int i = 1; i < nums1.length + 1; i++) {
            for (int j = 1; j < nums2.length + 1; j++) {
                if(nums1[i - 1] == nums2[j - 1]){
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                    if(dp[i][j] > result){
                        result = dp[i][j];
                    }
                }
            }
        }
        return result;
    }
    // dp[i][j] 以下标i - 1为结尾的A，和以下标j - 1为结尾的B，最长重复子数组长度为dp[i][j]。
    public int findLength3(int[] nums1, int[] nums2) {
       if(nums1 == null || nums2 == null) return 0;
       int max = 0;
       int n = nums1.length;
       int m = nums2.length;
       int[][] dp = new int[n + 1][m + 1];
        for (int i = 1; i < n + 1; i++) {
            for (int j = 1; j < m + 1; j++) {
                if(nums1[i - 1] == nums2[j - 1]){
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                    max = Math.max(max,dp[i][j]);
                }
            }
        }
        return max;
    }

}
